package com.cty.twentyThirdDay;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/*
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 * */
public class Q_33 {


      // 主包自己写的暴力算法 时间复杂度O(NlogN) 空间复杂度O(n) n为链表的长度
      public ListNode2 sortList(ListNode2 head) {
            ArrayList<ListNode2> listNode2s = new ArrayList<>();
            ListNode2 cur = head;
            while (cur != null) {
                  listNode2s.add(new ListNode2(cur.val));
                  cur = cur.next;
            }
            Collections.sort(listNode2s, new Comparator<ListNode2>() {
                  @Override
                  public int compare(ListNode2 o1, ListNode2 o2) {
                        return o1.val - o2.val;
                  }
            });
            // 排序好
            ListNode2 dummy = new ListNode2(0);
            cur = dummy;
            for (int i = 0;i < listNode2s.size();i++) {
                  cur.next = listNode2s.get(i);
                  cur = cur.next;
            }
            return dummy.next;
      }


      // 力扣官方题解 方法一:自顶向下归并排序
      /*
      * 思路:将链表都斩断 通过归并排序的思想
      *     一组为两个 两组维护一次 最后合并
      *     时间复杂度(NLogN) 空间复杂度O(1)
      * */
      public ListNode2 sortList2(ListNode2 head) {
            return divide(head,null);
      }
      // 分开的方法 传入节点的尾节点
      public ListNode2 divide(ListNode2 head,ListNode2 tail) {
            // 如果头节点是空的直接返回
            if (head == null) {
                  return head;
            }
            // 说明已经分到一组两个节点了 返回
            if (head.next == tail) {
                  // 将两个节点分开
                  head.next = null;
                  return head;
            }
           // 获得中间节点 可以用快慢指针的思维
            ListNode2 fast = head;
            ListNode2 slow = head;
            while (fast != tail) {
                  slow = slow.next;
                  fast = fast.next;
                  // 防止越过尾节点
                  if (fast != tail) {
                        fast = fast.next;
                  }
            }
            // 找到中间节点
            ListNode2 mid = slow;
            // 在继续分然后获得分开后在合成的子链表的头节点
            ListNode2 list1 = divide(head,mid);
            ListNode2 list2 = divide(mid, tail);
            // 合成新的节点
            ListNode2 ans = merge(list1,list2);
            return ans;
      }

      // 力扣官方题解 方法二:自底向上归并排序
      /*
      *  思路:
      *     首先将链表分成若干个子链表 链表的初始长度为subLength = 1;
      *     将链表最近的两个子链表的节点排序合成一个大点的链表
      *     返回 之后将后面的链表以同样的方式 当都进行完之后
      *     将subLength * 2 继续计算 最后一个链表长度可一
      *     小于subLength
      *
      * */
      public ListNode2 sortList3(ListNode2 head) {
            if (head == null) return head;
            ListNode2 node = head;
            int length = 0;
            while (node != null) {
                  length++;
                  node = node.next;
            }
            // 创建一个哑节点
            ListNode2 dummy = new ListNode2(0,head);
            for (int subLength = 1;subLength < length;subLength *= 2) {
                  // 获得当前节点
                  ListNode2 cur = dummy.next,prev = dummy;
                  while (cur != null) {
                        // 获取第一子链表的头部
                        ListNode2 head1 = cur;
                        for (int i = 1;i < subLength && cur.next != null;i++) {
                              cur = cur.next;
                        }
                        // 获得第二个子链表的头部
                        ListNode2 head2 = cur.next;
                        // 将第一个子链表断开
                        cur.next = null;
                        // 断开向前移动
                        cur = head2;
                        // 防止此时cur正好是链表的末尾
                        for (int i = 1;i < subLength && cur != null && cur.next != null;i++) {
                              cur = cur.next;
                        }
                        ListNode2 next = null;
                        if (cur != null) {
                              next = cur.next;
                              cur.next = null;
                        }
                        ListNode2 merge = merge(head1, head2);
                        prev.next = merge;
                        while (prev.next != null) {
                              prev = prev.next;
                        }
                        cur = next;
                  }
            }
            return dummy.next;
      }

      // 合成的方法
      public ListNode2 merge(ListNode2 list1,ListNode2 list2) {
            // 创建一个哑节点
            ListNode2 dummy = new ListNode2(0);
            ListNode2 temp = dummy,temp1 = list1,temp2 = list2;
            // 开始遍历两个要合成的头节点
            while (temp1 != null && temp2 != null) {
                  if (temp1.val <= temp2.val) {
                        temp.next = temp1;
                        temp1 = temp1.next;
                  } else {
                        temp.next = temp2;
                        temp2 = temp2.next;
                  }
                  temp = temp.next;
            }
            // 将剩余的元素加入目标链表的尾部 因为是链表直接加在尾部即可
            if (temp1 != null) {
                  temp.next = temp1;
            } else if(temp2 != null){
                  temp.next = temp2;
            }
            // 返回目标节点
            return dummy.next;
      }
}

class ListNode2 {
    int val;
    ListNode2 next;

    ListNode2() {
    }

    ListNode2(int val) {
        this.val = val;
    }

    ListNode2(int val, ListNode2 next) {
        this.val = val;
        this.next = next;
    }
}
